package com.LeeCode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 最小体力消耗路径
 */

public class Code1631 {
    public static void main(String[] args) {
        int[][] heights = {
                {1, 2, 2},
                {3, 8, 2},
                {5, 3, 5}
        };
        System.out.println(new Code1631().minimumEffortPath(heights));
    }

    // 四个方向：上、右、下、左
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int minimumEffortPath(int[][] heights) {
        int left = -1, right = 1_000_000;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(heights, mid))
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private boolean check(int[][] heights, int limit) {
        int row = heights.length, col = heights[0].length;
        boolean[][] visited = new boolean[row][col];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int[] direction : DIRECTIONS) {
                int nr = r + direction[0], nc = c + direction[1];
                if (nr >= 0 && nr < row && nc >= 0 && nc < col && !visited[nr][nc]) {
                    // 高度差小于等于limit才能同行
                    if (Math.abs(heights[r][c] - heights[nr][nc]) <= limit) {
                        visited[nr][nc] = true;
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return visited[row - 1][col - 1];
    }
}
